import java.util.Arrays;
import java.util.Comparator;
import java.util.Iterator;
import java.util.NoSuchElementException;

/**
 * Code from http://www.princeton/
 * 
 * @author Team Turtle
 *
 * @param <Key>
 */
public class CongressPQ<Key> implements Iterable<Key> {

	private Key[] pq; // store items at indices 1 to N
	private int N; // number of items on priority queue
	private Comparator<Key> comparator; // optional Comparator

	/**
	 * Create an empty priority queue.
	 */
	public CongressPQ() {
		this(1);
	}

	/**
	 * Create an empty priority queue with the given initial capacity.
	 */
	public CongressPQ(int capacity) {
		pq = (Key[]) new Object[capacity + 1];
		N = 0;
	}

	/**
	 * Create an empty priority queue with the given initial capacity, using the
	 * given comparator.
	 */
	public CongressPQ(int initCapacity, Comparator<Key> comparator) {
		this.comparator = comparator;
		pq = (Key[]) new Object[initCapacity + 1];
		N = 0;
	}

	/**
	 * Create a priority queue with the given items. Takes time proportional to
	 * the number of items using sink-based heap construction.
	 */
	public CongressPQ(Key[] keys) {
		N = keys.length;
		pq = (Key[]) new Object[keys.length + 1];
		for (int i = 0; i < N; i++)
			pq[i + 1] = keys[i];
		for (int k = N / 2; k >= 1; k--)
			sink(k);
		assert isMaxHeap();
	}

	/**
	 * Is the priority queue empty?
	 */
	public boolean isEmpty() {
		return N == 0;
	}

	/**
	 * Return the number of items on the priority queue.
	 */
	public int size() {
		return N;
	}

	/**
	 * Return the largest key on the priority queue. Throw an exception if the
	 * priority queue is empty.
	 */
	public Key max() {
		if (isEmpty())
			throw new RuntimeException("Priority queue underflow");
		return pq[1];
	}

	// helper function to double the size of the heap array
	private void resize(int capacity) {
		assert capacity > N;
		Key[] temp = (Key[]) new Object[capacity];
		for (int i = 1; i <= N; i++)
			temp[i] = pq[i];
		pq = temp;
	}

	/**
	 * Add a new key to the priority queue.
	 */
	public void insert(Key x) {

		// double size of array if necessary
		if (N >= pq.length - 1)
			resize(2 * pq.length);

		// add x, and percolate it up to maintain heap invariant
		pq[++N] = x;
		swim(N);
		assert isMaxHeap();
	}

	/**
	 * Delete and return the largest key on the priority queue. Throw an
	 * exception if the priority queue is empty.
	 */
	public Key delMax() {
		if (N == 0)
			throw new RuntimeException("Priority queue underflow");
		Key max = pq[1];
		exch(1, N--);
		sink(1);
		pq[N + 1] = null; // to avoid loitering and help with garbage collection
		if ((N > 0) && (N == (pq.length - 1) / 4))
			resize(pq.length / 2);
		assert isMaxHeap();
		return max;
	}

	/***********************************************************************
	 * Helper functions to restore the heap invariant.
	 **********************************************************************/

	private void swim(int k) {
		while (k > 1 && less(k / 2, k)) {
			exch(k, k / 2);
			k = k / 2;
		}
	}

	private void sink(int k) {
		while (2 * k <= N) {
			int j = 2 * k;
			if (j < N && less(j, j + 1))
				j++;
			if (!less(k, j))
				break;
			exch(k, j);
			k = j;
		}
	}

	/***********************************************************************
	 * Helper functions for compares and swaps.
	 **********************************************************************/
	private boolean less(int i, int j) {
		if (comparator == null) {
			return ((Comparable<Key>) pq[i]).compareTo(pq[j]) < 0;
		} else {
			return comparator.compare(pq[i], pq[j]) < 0;
		}
	}

	private void exch(int i, int j) {
		Key swap = pq[i];
		pq[i] = pq[j];
		pq[j] = swap;
	}

	// is pq[1..N] a max heap?
	private boolean isMaxHeap() {
		return isMaxHeap(1);
	}

	// is subtree of pq[1..N] rooted at k a max heap?
	private boolean isMaxHeap(int k) {
		if (k > N)
			return true;
		int left = 2 * k, right = 2 * k + 1;
		if (left <= N && less(k, left))
			return false;
		if (right <= N && less(k, right))
			return false;
		return isMaxHeap(left) && isMaxHeap(right);
	}

	public Iterator<Key> iterator() {
		return new HeapIterator();
	}

	private class HeapIterator implements Iterator<Key> {

		// create a new pq
		private CongressPQ<Key> copy;

		// add all items to copy of heap
		// takes linear time since already in heap order so no keys move
		public HeapIterator() {
			if (comparator == null)
				copy = new CongressPQ<Key>(size());
			else
				copy = new CongressPQ<Key>(size(), comparator);
			for (int i = 1; i <= N; i++)
				copy.insert(pq[i]);
		}

		public boolean hasNext() {
			return !copy.isEmpty();
		}

		public void remove() {
			throw new UnsupportedOperationException();
		}

		public Key next() {
			if (!hasNext())
				throw new NoSuchElementException();
			return copy.delMax();
		}
	}

	public static void main(String[] args) {

		int totalSeats, numStates, population;
		CongressPQ pq;	  // priority queue 

		State st; 		  // a state
		String inputLine; // an input line

		// number of states
		numStates = Integer.parseInt(StdIn.readLine());

		// number of seats
		totalSeats = Integer.parseInt(StdIn.readLine());
		// System.out.println(totalSeats);

		// array of states
		State[] a = new State[numStates];

		int i = 0;
		while (!StdIn.isEmpty()) {
			inputLine = StdIn.readLine(); 	 				 // read name
			population = Integer.parseInt(StdIn.readLine()); // read population
			a[i] = new State(inputLine, population);		 // create object
			i++; 
			totalSeats--;									 // decrement seats
		}
		
		// TIMER start
		Stopwatch timer = new Stopwatch();
		
		// Distribution of seats. 
		while (totalSeats > 0) {		// Do until no more seats left:
			pq = new CongressPQ(a);		// make priority queue,
			st = (State) pq.delMax();	// remove "biggest" from queue,
			st.incChairs(); 			// increments number of chairs, 
			totalSeats--;   			// decrement seats,
			pq = null;					// avoid loitering.
		}
		
		// TIMER stop		
		double time_consumption = timer.elapsedTime();
		
		// To print the results
		// Make an array of strings ( state name + state seats ) 
		String[] strs = new String[numStates];
		for (int k = 0; k < a.length; k++) {
			strs[k] = a[k].getName() + " " + a[k].getChairs();
		}

		Arrays.sort(strs);	// sort by comparing number of seats
							// print out sorted result
		for (String item : strs) {
			System.out.println(item);
		}
							// Aaand... here comes the overall time consumption.
		System.out.println("Tidsforbrug: " + time_consumption);	
	}
}
